/*
 * Copyright (C), 2015-2018
 * FileName: Solution018
 * Author:   zhao
 * Date:     2018/11/15 18:16
 * Description: 18. 四数之和
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈18. 四数之和〉
 *
 * @author zhao
 * @date 2018/11/15 18:16
 * @since 1.0.1
 */
public class Solution018 {

    /**************************************
     * 题目
     给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

     注意：

     答案中不可以包含重复的四元组。

     示例：

     给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

     满足要求的四元组集合为：
     [
     [-1,  0, 0, 1],
     [-2, -1, 1, 2],
     [-2,  0, 0, 2]
     ]
     **************************************/

    /**************************************
     *
     * 想法：
     *      1. 暴力破解：四层循环 一把梭
     *      2. 套用三层循环的思维
     *          原来 循环一次加滑动列表 改成 循环两次加滑动列表
     *          详细可以看这个：
     *          复杂度：n3/n
     *
     * 我的做法
     *      超过91%的测试案例
     *      时间复杂度/空间复杂度：n3/n
     * 代码执行过程：
     *
     * 总结：
     *      1. 之前卡在这题没有去做，就是自己没有想着动手写
     * ***********************************/
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) {
            return Collections.EMPTY_LIST;
        }
        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {

            // 如果和之前那个数据相同，则会是重复事件
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int valI = nums[i];

            for (int j = i + 1; j < nums.length - 2; j++) {

                // 如果和之前那个数据相同，则会是重复事件
                if (j - i > 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int valJ = nums[j];

                int leftIndex = j + 1;
                int rightIndex = nums.length - 1;

                while (leftIndex < rightIndex) {
                    int tmpVal = nums[leftIndex] + nums[rightIndex] + valI + valJ;

                    if (tmpVal > target) {
                        rightIndex--;
                    } else if (tmpVal < target) {
                        leftIndex++;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[leftIndex]);
                        list.add(nums[rightIndex]);
                        result.add(list);
                        // 用nums[leftIndex] == nums[leftIndex + 1]控制重复
                        while (leftIndex < rightIndex && nums[leftIndex] == nums[leftIndex + 1]) {
                            leftIndex++;
                        }
                        while (leftIndex < rightIndex && nums[rightIndex] == nums[rightIndex - 1]) {
                            rightIndex--;
                        }
                        leftIndex++;
                        rightIndex--;
                    }
                }
            }
        }
        return result;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<List<Integer>> better(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int len = nums.length;
        if (nums == null || len < 4) {
            return result;
        }
        //排序
        Arrays.sort(nums);
        //确定两个值两层循环然后确定左右指针
        //外循环
        for (int i = 0; i < len - 3; i++) {
            //判断相等
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //最小值大于目标值结束
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            //最大值小于目标值跳过此循环
            if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target) {
                continue;
            }
            //内循环
            for (int j = i + 1; j < len - 2; j++) {
                //判断相等
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                //最小值大于目标值结束
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                //最大值小于目标值跳过此循环
                if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {
                    continue;
                }
                //左右指针寻找满足条件的值
                int left = j + 1;
                int right = len - 1;
                while (left < right) {
                    int sum = nums[left] + nums[right] + nums[i] + nums[j];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }

                }
            }
        }
        return result;
    }

}
